/**
 * @Author Fizz Pu
 * @Date 2020/11/8 下午5:14
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.Arrays;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 示例 2：
 *
 * 输入：coins = [2], amount = 3
 * 输出：-1
 * 示例 3：
 *
 * 输入：coins = [1], amount = 0
 * 输出：0
 * 示例 4：
 *
 * 输入：coins = [1], amount = 1
 * 输出：1
 * 示例 5：
 *
 * 输入：coins = [1], amount = 2
 * 输出：2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

// 方案1 dfs + 剪枝

// 方案2 bfs

// 方案3 dp
/**
 * [1,2,5] 11
 * dp[i] 金额为i需要的最小钞票数, dp[0] = 0
 * dp[1]  = 1 dp[2] = 1 dp[5] = 1
 * dp[3] = min(dp[3-1],dp[3-1]) + 1 = 2
 * dp[4] = min(dp[4-1], dp[4-2]) + 1 = 2
 * dp[5] = min(dp[5-1], dp[5-2], dp[5-5]) + 1 = 1
 */

// 1.dp[amount+1], dp[0] = 0
// 2. 遍历数组, dp[i] = dp[i-coin] + 1, 其中coin <= i
// 3. 注意处理解不存在的情况, 采用标志位
public class Lee322 {
    public int coinChange(int[] coins, int amount) {
        if(amount <= 0)return 0;

        int[] dp = new int[amount+1];
        dp[0] = 0;


        for(int i = 1; i < amount+1; ++i){
            int min = Integer.MAX_VALUE;
            int flag = 0; // 表示是否可以交换
            for(int coin : coins){
                if(coin <= i && dp[i-coin] != -1){
                    flag = 1;
                    min = Math.min(dp[i-coin] + 1, min) ;
                }
            }
            if(flag == 1) dp[i] = min;
            else dp[i] = -1;
        }

        return dp[amount];
    }


    public static void main(String[] args) {
        Lee322 lee322 =  new Lee322();
        System.out.println(lee322.coinChange(new int[]{1,2,5}, 12));
        System.out.println(lee322.coinChange(new int[]{2}, 1));
        System.out.println(lee322.coinChange(new int[]{1}, 1));
        System.out.println(lee322.coinChange(new int[]{1}, 2));
        System.out.println(lee322.coinChange(new int[]{1}, 0));
        System.out.println(lee322.coinChange(new int[]{2,5,10,1}, 27));
    }
}

